package com.zklh.leetcode.tree.middle;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * @author ：tong nan
 * @date ：Created in 2021/5/24 17:38
 * @description ：二叉树序列化和反序列化
 * @modifiedBy ：
 */
public class BinaryTreeCodeC {

    private final String separator = ",";
    private final String placeholder = "#";

    /**
     * 序列化
     * @param root
     * @return
     */
    public String serialize(TreeNode root) {
        if(root == null) {
            return placeholder;
        }
        return root.val + separator  + serialize(root.left) +separator+  serialize(root.right);
    }

    /**
     * 反序列化
     * @param data
     * @return
     */
    public TreeNode deserialize(String data) {
        DeserializeContext context = new DeserializeContext();
        context.location = 0;
        String[] charArr = data.split(separator);
        return deserialize(charArr, context);
    }

    private TreeNode deserialize(String[] chars, DeserializeContext context) {

        if (chars[context.location].equals(placeholder)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(chars[context.location]));
        context.location += 1;
        node.left = deserialize(chars, context);
        context.location += 1;
        node.right = deserialize(chars, context);
        return node;
    }

    private static class DeserializeContext{
        // 当前遍历过程中结点所处的位置(在data中)
        int location;

    }


    public static void main(String[] args) {

        TreeNode node = new TreeNode(2);
        node.left = new TreeNode(1);
        node.right = new TreeNode(3);
        node.left.right = new TreeNode(6);
        BinaryTreeCodeC c = new BinaryTreeCodeC();
        String s = c.serialize(node);

        TreeNode newNode = c.deserialize(s);

    }

}
